#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//目标：
//1：前序（根，左，右）； 中序（左， 右， 根）；后序（左，右， 根）的遍历（递归）+ 层序（队列）
//2:判断是否是完全二叉树
//3：总节点个数， 叶子节点的个数，第K层的节点个数，二叉树的深度

//Binary tree（二叉树）
typedef int BTDateType;
typedef struct BTNode
{
	BTDateType val;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

BTNode* CreateNode(BTDateType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	assert(newnode);
	newnode->val = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}


//先序遍历
void PrevOrder(BTNode* root)
{
	if (root == NULL)
		return;
	printf("%d ", root->val);//根
	PrevOrder(root->left);//左树
	PrevOrder(root->right);//右树
}


//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
		return;
	InOrder(root->left);//左树
	printf("%d ", root->val);//根
	InOrder(root->right);//右树
}


//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
		return;
	PostOrder(root->left);//左树
	PostOrder(root->right);//右树
	printf("%d ", root->val);//根
}



//层序（队列）

typedef  BTNode* QDateType;
typedef struct QListNode
{
	QDateType val;
	struct QListNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;

void LayerOrder(QDateType root)
{
	//创建队列
	Queue src;
	//初始化队列
	QueueInit(&src);
	//如果不为空树，先将根入队
	if (root != NULL)
		QueuePush(&src, root);

	while (!QueueEmpty(&src))
	{
		//输出队头
		QDateType front = QueueFront(src);
		printf("%d ", front->val);
		//将队头出队
		QueuePop(&src);
		//再将左右子树的根入队
		if (front->left != NULL)
			QueuePush(&src, front->left);
		if (front->right != NULL)
			QueuePush(&src, front->right);
	}
}

//判断一棵树是不是完全二叉树
//利用层序，完全二叉树的NULL节点是连续的
bool IsFullBinaryTree(QDateType root)
{
	//创建队列
	Queue src;
	//初始化队列
	QueueInit(&src);
	//先将根节点入队
	if (root == NULL)
		return false;
	QueuePush(&src, root);

	while (!QueueEmpty(&src))
	{
		//获取队头，判断是否为NULL
		QDateType front = QueueFront(src);
		//将队头出队
		QueuePop(&src);
		//判断
		if (front == NULL)
			break;
		//再将左右子树的根入队(NULL也要入队)
		QueuePush(&src, front->left);
		QueuePush(&src, front->right);
	}

	//接着判断NULL 是否连续
	while (!QueueEmpty(&src))
	{
		QDateType front = QueueFront(src);
		QueuePop(&src);
		if (front != NULL)
			break;
	}
	if (QueueEmpty(&src))
	{
		QueueDestroy(&src);//队列销毁
		return true;
	}
	else
	{
		QueueDestroy(&src);
		return false;
	}
}



//所有节点总个数
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}



//叶子节点的个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}


//第K层节点个数
int BinaryTree_K_Size(BTNode* root, int k)
{
	//根的K-1层的左子树右节点树的和，当递归到k==1时停止
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTree_K_Size(root->left, k - 1) + BinaryTree_K_Size(root->right, k - 1);
}


//深度
int MaxDepth(BTNode* root)
{
	//根的深度1 + fmax(左子树，右子树)
	if (root == NULL)
		return 0;
	return 1 + fmax(MaxDepth(root->left), MaxDepth(root->right));
}




//销毁(后序)
void BinaryTreeDestroy(BTNode** root)
{
	if (*root == NULL)
		return;
	BinaryTreeDestroy(&((*root)->left));
	BinaryTreeDestroy(&((*root)->right));
	free(*root);
	*root = NULL;
}

//主函数入口
int main()
{
	
	BTNode* node1 = CreateNode(1);
	BTNode* node2 = CreateNode(2);
	BTNode* node3 = CreateNode(3);
	BTNode* node4 = CreateNode(4);
	BTNode* node5 = CreateNode(5);
	BTNode* node6 = CreateNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	//先序遍历
	PrevOrder(node1);
	printf("\n");
	//中序遍历
	InOrder(node1);
	printf("\n");
	//后序遍历
	PostOrder(node1);
	printf("\n");

	//节点总个数
	printf("%d\n",BinaryTreeSize(node1));
	//叶子节点的个数
	printf("%d\n", BinaryTreeLeafSize(node1));
    //第K层的节点个数
	printf("%d\n", BinaryTree_K_Size(node1, 2));
	//二叉树的深度
	MaxDepth(node1);

	//销毁
	BinaryTreeDestroy(&node1);
	return 0;
}